package sliding_window

/*

给你两个字符串s1和s2 ，写一个函数来判断 s2 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
*/

//判断 s 中是否存在 t 的排列
func checkInclusion(t string, s string) bool {
	//初始化
	need, window := make(map[byte]int), make(map[byte]int)
	//个数初始化
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	left, right, valid := 0, 0, 0

	for right < len(s) {

		//扩大窗口
		// c是将移入窗口的字符
		c := s[right]
		//右移窗口
		right++
		//进行窗口内数据的一系列更新
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}

		//判断左侧窗口是否要收缩
		//使用一个固定长度为len(t)的滑动窗口来维护
		for right-left >= len(t) {
			//找到的合法的排列
			if valid == len(need) {
				return true
			}

			//d 是将要移出窗口的字符
			d := s[left]
			//左移窗口，收缩窗口，得到可行解
			left++
			//进行窗口内数据的一系列更新，进行最小覆盖子串的更新，以得到最优解
			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}

	return false
}
